/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.google.code.peersim.pastry.protocol;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * According to the Pastry specification, a Pastry routing table is primarly characterized
 * by the {@link PastryProtocol#getB()} parameter. This parameter affects the routing table
 * number of columns being {@code 2^b-1}.<br>
 * Each non-empty routing-table entry must store, at least, the IP-address of a Pastry node
 * along with its {@link PastryId}.<br>
 * Rows have also a fundamental meaning: each entry stored at row {@code r} shares with the
 * node the routing-table belongs to exactly the first {@code r} characters of its {@link PastryId}
 * representation in radix {@code 2^b} (see {@link PastryId#forRouting()}).<br>
 * Moreover, an entry stored in row {@code r} and column {@code c}, must have the {@code c}-th
 * digit (of its {@link PastryId#forRouting()}) equal to the {@code c}-th character of the radix used to
 * represent the {@link PastryId} as a string.<br>
 * Due to the uniform distribution that must be followed when assigning {@link PastryId}s,
 * on average only {@code ceiling(log(N)) (where the log is in base 2^b)} rows are populated.<br>
 * <b>Note:</b> both rows and columns are zero-based.
 *
 * @author frusso
 * @version 0.1
 * @since 0.1
 */
final class PastryRoutingTable {

  /**
   * {@link PastryId} of the node that owns this routing table instance.
   */
  private final PastryId ownerId;
  /**
   * The routing table.
   */
  private final Map<Integer, Map<Character, PastryNodeDescriptor>> routingTable;

  /**
   * Constructor.
   * 
   * @param b The {@link PastryProtocol#getB()} Pastry's configuration parameter
   */
  PastryRoutingTable(PastryId id) {
    ownerId = id;
    routingTable = new HashMap<Integer, Map<Character, PastryNodeDescriptor>>();
  }

  /**
   * Adds the given {@link Entry} to the current routing table, replacing any already existing value,
   * according to the following rules:
   * <ol>
   * <li>the row is given by the lenght of the prefix shared by {@code entry} and this
   * routing table owner's {@link PastryId} according to the definition of
   * {@link PastryId#sharedPrefixLength(com.google.code.peersim.pastry.protocol.PastryId)}</li>
   * <li>the column is given by the numeric value of the first non-matching char of
   * {@code entry} when compared to this routing table owner's {@link PastryId} according to the definition of
   * {@link PastryId#firstNonMatchingCharDigit(com.google.code.peersim.pastry.protocol.PastryId)}</li>
   * </ol>
   *
   * @param entry The entry to be added
   */
  final void add(PastryNodeDescriptor entry) {
    PastryId entryId = entry.getPastryId();
    if(!this.ownerId.equals(entryId)) {
      int row = entryId.sharedPrefixLength(ownerId);
      Character col = entryId.firstNonMatchingChar(ownerId);
      if(col!=null) {
        Map<Character, PastryNodeDescriptor> r = routingTable.get(row);
        if (r == null) {
          r = new HashMap<Character, PastryNodeDescriptor>();
          routingTable.put(row, r);
        }
        r.put(col, entry);
      } else {
        // this should never happen
        throw new IllegalStateException("Trying to add the owner id to its own routing-table.");
      }
    }
  }

  /**
   * Adds the given {@link Entry} to the current routing table, iff there is no value
   * already stored at the coordinates computed as stated in
   * {@link PastryRoutingTable#add(com.google.code.peersim.pastry.protocol.PastryNodeDescriptor)}.
   *
   * @see PastryRoutingTable#add(com.google.code.peersim.pastry.protocol.PastryNodeDescriptor)
   * @param entry The entry to be added
   * @return {@link Boolean#TRUE} iff the entry has been added, {@link Boolean#FALSE} otherwise
   */
  final boolean addIfEmpty(PastryNodeDescriptor entry) {
    boolean added = false;
    PastryId entryId = entry.getPastryId();
    if(!this.ownerId.equals(entryId)) {
      int row = entryId.sharedPrefixLength(ownerId);
      Character col = entryId.firstNonMatchingChar(ownerId);
      Map<Character, PastryNodeDescriptor> r = routingTable.get(row);
      if(r==null) {
        r = new HashMap<Character, PastryNodeDescriptor>();
        routingTable.put(row, r);
      }
      if(!r.containsKey(col)) {
        // add can proceede
        r.put(col, entry);
        added = true;
      }
    }
    return added;
  }

  /**
   * Tells whether this table contains the given node or not.
   *
   * @param node The node
   * @return Whether it is stored in this table or not
   */
  boolean contains(PastryNode node) {
    boolean found = true;
    PastryId entryId = node.getPastryId();
    int row = entryId.sharedPrefixLength(ownerId);
    Map<Character, PastryNodeDescriptor> r = routingTable.get(row);
    if(r==null) {
      found = false;
    } else {
      Character col = entryId.firstNonMatchingChar(ownerId);
      if(!r.containsKey(col)) {
        found = false;
      } else {
        PastryNodeDescriptor pnd = r.get(col);
        if(!pnd.getPastryId().equals(entryId)) {
          found = false;
        }
      }
    }
    return found;
  }

  /**
   * Empties the whole routing table.
   */
  final void empty() {
    this.routingTable.clear();
  }

  /**
   * Returns the content stored for the given {@code key}.
   *
   * @param key
   * @return
   */
  final PastryNodeDescriptor get(PastryId key) {
    PastryNodeDescriptor res = null;
    int shl = key.sharedPrefixLength(ownerId);
    Character col = key.firstNonMatchingChar(ownerId);
    if(col!=null) {
      res = get(shl, col);
    }
    return res;
  }

  /**
   * Returns an immutable {@link Entry} found at the given coordinates in the
   * routing table. The returned result might also be {@code null} should there
   * be nothing stored.
   *
   * @param row The row
   * @param col The column
   * @return The {@link Entry} or {@code null}
   */
  final PastryNodeDescriptor get(int row, char col) {
    PastryNodeDescriptor entry = null;
    Map<Character, PastryNodeDescriptor> r = routingTable.get(row);
    if (r != null) {
      entry = r.get(col);
    }
    return entry;
  }

  /**
   * Returns an unmodifiable view of all the stored nodes.
   *
   * @return An unmodifiable view of all the stored nodes
   */
  final List<PastryNode> getAllNodes() {
    List<PastryNode> list = new ArrayList<PastryNode>();
    Collection<Map<Character, PastryNodeDescriptor>> rows = routingTable.values();
    for (Map<Character, PastryNodeDescriptor> row : rows) {
      Collection<PastryNodeDescriptor> entries = row.values();
      for (PastryNodeDescriptor entry : entries) {
        list.add(entry.getPastryNode());
      }
    }
    return Collections.unmodifiableList(list);
  }

  /**
   * Returns the given row.
   * @param row The row index
   * @return The row or an empty set
   */
  Set<PastryNodeDescriptor> getRow(int row) {
    // TODO is the following condition right?
    if(row<=this.ownerId.getForRoutingLength()) {
      Map<Character,PastryNodeDescriptor> entries = routingTable.get(row);
      if(entries!=null)
        return Collections.unmodifiableSet(new HashSet<PastryNodeDescriptor>(entries.values()));
      else
        return Collections.EMPTY_SET;
    } else {
      throw new IndexOutOfBoundsException("Trying to access routing table at row "+row+" while limit is "+this.ownerId.getForRoutingLength());
    }
  }

  /**
   * Tells if the routing-table is empty.
   * @return
   */
  final boolean isEmpty() {
    return this.routingTable.isEmpty();
  }

  /**
   * Updates the current {@link PastryRoutingTable} instance using the information
   * stored in the provided instance named {@code that}. This means that {@code that}'s
   * entry with coordinates {@code [x,y]} will be used to populate {@code this}'s entry of
   * coordinates {@code [x,y]} iff the latter stores no content.
   * Should {@code that} be empty or {@code null}, this method would simply do nothing.
   *
   * @param that The data structure used to update the current one
   * @return The current updated data structure
   */
  final PastryRoutingTable merge(PastryRoutingTable that) {
    if (that != null && !that.isEmpty()) {
      Collection<Map<Character, PastryNodeDescriptor>> rows = that.routingTable.values();
      for (Map<Character, PastryNodeDescriptor> row : rows) {
        Collection<PastryNodeDescriptor> entries = row.values();
        for (PastryNodeDescriptor entry : entries) {
          addIfEmpty(entry);
        }
      }
    }
    return this;
  }

  /**
   * Removes the given node.
   *
   * @param pnd The node to remove
   */
  void remove(PastryNodeDescriptor pnd) {
    PastryId id = pnd.getPastryId();
    int r = id.sharedPrefixLength(ownerId);
    char c = id.firstNonMatchingChar(ownerId);
    Map<Character,PastryNodeDescriptor> row = routingTable.get(r);
    if(row!=null) {
      row.remove(c);
    }
  }

  /**
   * Returns the number of stored entries.
   * @return
   */
  final int size() {
    int size = 0;
    Set<Map.Entry<Integer, Map<Character, PastryNodeDescriptor>>> rows = routingTable.entrySet();
    for (Map.Entry<Integer, Map<Character, PastryNodeDescriptor>> row : rows) {
      Map<Character, PastryNodeDescriptor> _row = row.getValue();
      size += _row.size();
    }
    return size;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public final String toString() {
    StringBuilder rt = new StringBuilder();
    Set<Map.Entry<Integer,Map<Character,PastryNodeDescriptor>>> entries = routingTable.entrySet();
    for(Map.Entry<Integer,Map<Character,PastryNodeDescriptor>> entry : entries) {
      int rowNum = entry.getKey();
      Map<Character,PastryNodeDescriptor> row = entry.getValue();
      Set<Map.Entry<Character,PastryNodeDescriptor>> nodes = row.entrySet();
      for(Map.Entry<Character,PastryNodeDescriptor> node : nodes) {
        char colNum = node.getKey();
        PastryNodeDescriptor pnd = node.getValue();
        rt.append("["+rowNum+","+colNum+"] -> "+pnd+"\n");
      }
    }
    return "PROPERTIES [owner: " + ownerId.forRouting() + "]\n" + rt.toString();
  }
}